package 剑指offer.字符串;

/**
 * @link https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 * <p>
 * TODO 正则1
 * <p>
 * 实现一个函数用来匹配包含 . 和 * 的正则表达式
 * . 可以代表任意一个字符
 * * 代表它前面的一个字符可以出现任意次（含 0 次）
 * 例如：字符串 aaa 可以和 a.a 以及 ab*ac*a 匹配（b*此时等于没有出现）
 */
public class 第19题正则表达式匹配 {

    public static boolean match(char[] str, char[] pattern) {
        return matchStr(str, 0, pattern, 0);
    }


    public static boolean matchStr(char[] str, int i, char[] pattern, int j) {

        if (i == str.length && j == pattern.length) {
            // 字符串和模式串都为空
            return true;
        }

        if (j == pattern.length) {
            // 模式串为空
            return false;
        }

        // 模式串下一个字符是否是'*'
        boolean next = (j + 1 < pattern.length && pattern[j + 1] == '*');
        /*
            aaa

            a.a

            ab*ac*a

            a.*ac*a

         */
        if (next) {
            // 模式串与当前的 str指向的数值一样，就让他们各自前进，j 前进 2 位跳过 * 号
            if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
                /*
                注意这里存在两种情况：

                一种是字符串不动，模式串移动两个以跳过 * 号（因为*可以代0个字符）。

                另一种是*号代表多个字符，即字符串移动一个，但是模式串不动
                （因为 * 可以代表多个它前面的字符，但是具体是多少个我们不知道，只能让字符串移动，但是只要能进入这个判断条件里面，就代表着匹配成功
                    最后字符串会走到匹配失败，但是模式串留在原地，此时进入else语句）

                else 语句里面就是属于只让模式串移动两个位置的算法，此时模式串会快速匹配上文中字符串移动的个数（这也就代表着*究竟代表着几个字符）
                */
                return matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j);
            } else {
                // 模式串需要忽略 * 前面的所有数值
                return matchStr(str, i, pattern, j + 2);
            }
        } else {
            if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
                // 最理想的情况就是模式串和字符串都是一样的，不同的话应该都是 .
                return matchStr(str, i + 1, pattern, j + 1);
            } else {
                return false;
            }
        }
    }

    public static void main(String[] args) {
        char[] str = "aaaa".toCharArray();
//        char[] pattern = "a.a".toCharArray();
//        char[] pattern = "ab*ac*a".toCharArray();
        char[] pattern = "a.*".toCharArray();
        System.out.println(match(str, pattern));
    }
}
